package sort

//冒泡
func BubbleSort(old []int) {
	for i := len(old) - 1; i > 0; i-- {
		for j := 0; j < i; j++ {
			if old[j] > old[j+1] {
				old[j], old[j+1] = old[j+1], old[j]
			}
		}
	}
}

//选择
func SelectSort(old []int) {
	for i := 0; i < len(old); i++ {
		min_i := i
		for j := i + 1; j < len(old); j++ {
			if old[min_i] > old[j] {
				min_i = j
			}
		}
		old[i], old[min_i] = old[min_i], old[i]
	}
}

//插入
func InsertSort(old []int) {
	for i := 1; i < len(old); i++ {
		if old[i] < old[i-1] {
			for j := i; j > 0; j-- {
				if old[j] > old[j-1] {
					break
				}
				old[j], old[j-1] = old[j-1], old[j]
			}
		}
	}
}

//快速
func QuickSort(old []int) {
	if len(old) <= 1 {
		return
	}

	l, r := 0, len(old)-1
	mid := old[0]
	for l < r {
		for l < r && old[r] >= mid {
			r--
		}
		for l < r && old[l] <= mid {
			l++
		}

		if l < r {
			old[r], old[l] = old[l], old[r]
		}
	}
	old[r], old[0] = old[0], old[r]

	QuickSort(old[:r])
	QuickSort(old[r+1:])
}

//希尔(分组插入)
func ShellSort(old []int) {
	for step := len(old) / 2; step > 0; step /= 2 {
		for i := step; i < len(old); i++ {
			for j := i; j-step >= 0; j -= step {
				if old[j] < old[j-step] {
					old[j], old[j-step] = old[j-step], old[j]
				} else {
					break
				}
			}
		}
	}
}

//归并
func MergeSort(old []int) []int {
	if len(old) == 1 {
		return old
	}

	mid := len(old) / 2
	left := MergeSort(old[:mid])
	right := MergeSort(old[mid:])

	new_arr := func(left, right []int) []int {
		new_arr := make([]int, len(left)+len(right))
		a1, a2 := 0, 0
		i := 0
		for a1 < len(left) && a2 < len(right) {
			if left[a1] < right[a2] {
				new_arr[i] = left[a1]
				a1++
				i++
			} else {
				new_arr[i] = right[a2]
				a2++
				i++
			}
		}

		for a1 < len(left) {
			new_arr[i] = left[a1]
			a1++
			i++
		}
		for a2 < len(right) {
			new_arr[i] = right[a2]
			a2++
			i++
		}

		return new_arr
	}(left, right)

	copy(old, new_arr)

	return old
}

//堆
func HeapSort(old []int) {

}

//基数

//桶

//计数
